/*
** FileName:PriorityQueue.c
** Author:Creat
** Time:下午3:54
** Date:2024/5/26
**/
#include "stdlib.h"
#include "string.h"
#include "PriorityQueue.h"
// 初始化
int init(PriorityQueue **pq, int max_size, PriorityQueueCmpFunc cmp) {
    // 输入合法性
    if(max_size <= 0){
        return 0;
    }
    // 创建
    *pq = (PriorityQueue *) malloc(sizeof(PriorityQueue));
    // 创建失败
    if(*pq == NULL){
        return 0;
    }
    // 下标0保留，不适用
    (*pq)->data = (void **)malloc(sizeof(void *) * (max_size + 1));
    if((*pq)->data == NULL){
        free(pq);
        return 0;
    }
    // 初始化队列元素
    memset((*pq)->data, 0, sizeof(void*) * (max_size + 1));
    (*pq)->capacity = max_size;
    (*pq)->size = 0;
    (*pq)->cmp = cmp;
    return 1;
}
// 判空
int is_empty(PriorityQueue *pq){
    if(pq == NULL){
        return 0;
    }
    if(pq->size == 0){
        return 1;
    }
    else{
        return 0;
    }
}
// 判满
int is_full(PriorityQueue *pq){
    if(pq == NULL){
        return 0;
    }
    if(pq->size == pq->capacity){
        return 1;
    }
    else{
        return 0;
    }
}
// 插入
int push(PriorityQueue *pq, void *data){
    int i = 0; // 计数变量
    // 队列满，插入失败
    if(is_full(pq)){
        return 0;
    }
    for(i = pq->size + 1;pq->cmp(data, pq->data[i/2]) < 0 && i > 1;i /= 2){
        pq->data[i] = pq->data[i/2];
    }
    pq->data[i] = data;
    pq->size++;
    return 1;
}
// 找最值
void* peek(PriorityQueue *pq){
    if(pq == NULL){
        return NULL;
    }
    if(is_empty(pq)){
        return NULL;
    }
    return pq->data[1];
}
// 弹出第一个
void* pop(PriorityQueue *pq){
    int i = 1;
    int maxchild = 0;
    if(pq == NULL){
        return NULL;
    }
    if(is_empty(pq)){
        return NULL;
    }
    void* res = pq->data[1];
    void* last = pq->data[pq->size];
    pq->size--;
    // 将第一个元素作为空，下沉
    for(i = 1; i * 2 < pq->size;i = maxchild){
        maxchild = i * 2;
        // 空穴选取两个孩子中的最小值
        if(pq->cmp(pq->data[maxchild + 1], pq->data[maxchild]) < 0 && maxchild != pq->size){
            maxchild += 1;
        }
        // last 比空穴元素大，空穴继续下沉
        if(pq->cmp(last, pq->data[maxchild]) > 0){
            pq->data[i] = pq->data[maxchild];
        }
        else{
            break;
        }
    }
    pq->data[i] = last;
    return res;
}
// 销毁
int destroy(PriorityQueue *pq){
    if(pq == NULL){
        return 0;
    }
    free(pq->data);
    free(pq);
    return 1;
}